--- Day 13: A Maze of Twisty Little Cubicles ---
You arrive at the first floor of this new building to discover a much less welcoming environment than the shiny atrium of the last one. Instead, you are in a maze of twisty little cubicles, all alike.
Every location in this area is addressed by a pair of non-negative integers (x,y). Each such coordinate is either a wall or an open space. You can't move diagonally. The cube maze starts at 0,0 and seems to extend infinitely toward positive x and y; negative values are invalid, as they represent a location outside the building. You are in a small waiting area at 1,1.
While it seems chaotic, a nearby morale-boosting poster explains, the layout is actually quite logical. You can determine whether a given x,y coordinate will be a wall or an open space using a simple system:
Find x*x + 3*x + 2*x*y + y + y*y.
Add the office designer's favorite number (your puzzle input).
Find the binary representation of that sum; count the number of bits that are 1.
If the number of bits that are 1 is even, it's an open space.
If the number of bits that are 1 is odd, it's a wall.
For example, if the office designer's favorite number were 10, drawing walls as # and open spaces as ., the corner of the building containing 0,0 would look like this:
0123456789
0 .#.####.##
1 ..#..#...#
2 #....##...
3 ###.#.###.
4 .##..#..#.
5 ..##....#.
6 #...##.###
Now, suppose you wanted to reach 7,4. The shortest route you could take is marked as O:
0123456789
0 .#.####.##
1 .O#..#...#
2 #OOO.##...
3 ###O#.###.
4 .##OO#OO#.
5 ..##OOO.#.
6 #...##.###
Thus, reaching 7,4 would take a minimum of 11 steps (starting from your current location, 1,1).
What is the fewest number of steps required for you to reach 31,39?
Your puzzle input is 1362.
In [10]:
class Maze:
def __init__(self, n):
self.n = n
def is_wall(self, x, y):
return True if x < 0 or y < 0 else len("{0:b}".format(x*x + 3*x + 2*x*y + y + y*y + self.n).replace('0', '')) % 2 != 0
def show(self, width, height, path=None):
path = set() if path is None else set(path)
for y in range(height):
print("{} {}".format(y, "".join(['#' if self.is_wall(w, y) else ('O' if (w, y) in path else '.') for w in range(width)])))
def move(self, orig, dest):
movements = [([], orig)]
visited = set()
while len(movements) > 0:
path, pos = movements.pop(0)
if pos == dest:
return path + [pos]
visited.add(pos)
x, y = pos
movements += [(path + [pos], m) for m in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)] if not self.is_wall(*m) and m not in visited]
def upto(self, orig, distance):
movements = [([], orig)]
visited = set()
while len(movements) > 0:
path, pos = movements.pop(0)
visited.add(pos)
if len(path) < distance:
x, y = pos
movements += [(path + [pos], m) for m in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)] if not self.is_wall(*m) and m not in visited]
return visited
In [11]:
m = Maze(10)
m.show(10,7)
In [12]:
path = m.move((1,1), (7,4))
In [13]:
len(path) - 1
Out[13]:
In [14]:
m.show(10, 7, path=path)
In [15]:
%%time
m2 = Maze(1362)
path = m2.move((1,1), (31,39))
In [16]:
len(path) - 1
Out[16]:
--- Part Two ---
How many locations (distinct x,y coordinates, including your starting location) can you reach in at most 50 steps?
Your puzzle input is still 1362.
In [17]:
d = m2.upto((1,1), 50)
In [18]:
len(d)
Out[18]:
In [ ]: